package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/description/">I. 二叉搜索树的最近公共祖先</a>
 * <p>给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。<br>
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * </p>
 * <pre>
 *     例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
 *                            6
 *                         /    \
 *                        2      8
 *                       / \    / \
 *                      0   4  7  9
 *                         /\
 *                        3  5
 * </pre>
 *
 * @author c2b
 * @since 2023/3/22 13:25
 */
public class JzOffer0068LowestCommonAncestor_I_M {

    /**
     * @param root 根节点
     * @param p    节点p
     * @param q    节点q
     * @return 最近的公共节点
     * @author c2b
     * @since 2023/3/22 13:56
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val > root.val && q.val > root.val) {
                // p,q都在root节点的右侧
                root = root.right;
            } else if (p.val < root.val && q.val < root.val) {
                // p,q都在root节点的左侧
                root = root.left;
            } else {
                // 找到最近祖先：一个在左侧、一个在右侧。或者至少有一个节点是root节点。
                return root;
            }
        }
        return null;
    }

    /**
     * 两次遍历
     *
     * @param root 根节点
     * @param p    节点p
     * @param q    节点q
     * @return 最近的公共节点
     * @author c2b
     * @since 2023/3/22 13:56
     */
    public TreeNode lowestCommonAncestor2(final TreeNode root, final TreeNode p, final TreeNode q) {
        if (root == null) {
            return null;
        }
        final List<TreeNode> pPathList = getPath(root, p);
        final List<TreeNode> qPathList = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < pPathList.size() && i < qPathList.size(); i++) {
            if (pPathList.get(i) == qPathList.get(i)) {
                ancestor = pPathList.get(i);
            }
        }
        return ancestor;
    }

    /**
     * 获取路径
     *
     * @param root   根节点
     * @param target 目标节点
     * @return 目标节点走过的路径
     * @author c2b
     * @since 2023/3/22 14:03
     */
    private List<TreeNode> getPath(final TreeNode root, final TreeNode target) {
        final List<TreeNode> res = new ArrayList<>();
        TreeNode node = root;
        while (node != target) {
            res.add(node);
            if (node.val < target.val) {
                node = node.right;
            } else {
                node = node.left;
            }
        }
        // 将当前节点加入路径中
        res.add(node);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        final JzOffer0068LowestCommonAncestor_I_M jzOffer0068LowestCommonAncestor = new JzOffer0068LowestCommonAncestor_I_M();
        final TreeNode treeNode = jzOffer0068LowestCommonAncestor.lowestCommonAncestor(root, root.left, root.left.right);
        System.out.println(treeNode);
    }
}
